'''
Created on Jul 4, 2011

@author: vakumar
'''
from com.utils.util import Utils
#from com.sorts.sorter import Sorter

class QuickSorter(object):
    '''
    classdocs
    '''


    def __init__(self,arr):
        '''
        Constructor
        '''
        self.arr = arr
        
    def __partition(self, p, r):
        pvt = self.arr[r]
        i = p
        for j in range(p,r):
            if self.comparator(self.arr[j],pvt):
                self.arr[i], self.arr[j] = Utils.swapval(i, j, self.arr)
                i += 1
        self.arr[i], self.arr[r] = Utils.swapval(i, r, self.arr)
        return i
    
        
    def __quicksort(self,p, r):
        if p < r:
            q = self.__partition(p, r)
            self.__quicksort(p,q-1)
            self.__quicksort(q+1,r)
            
    def dosort(self):
        print '*'*20
        print 'Quick Sort'
        print '*'*20
        print 'before sort : %s' %str(self.arr)
        self.comparator = Utils.comparator() 
        self.__quicksort(0,len(self.arr)-1)
        print 'after sort : %s' %str(self.arr)
        print 'Comparision Performed:: %s' %Utils.count
        self.count = Utils.count 
        
    def getComparisonCount(self):
        return self.count 
        
    def sort(self):
        self.comparator = Utils.comparator()
        self.__quicksort(0, len(self.arr) -1)  
        self.count = Utils.count 
        
if __name__ == '__main__':
    arr = [3,4,2,7,1,9,5]
    q = QuickSorter(arr)
    q.dosort()
        